#include "Hash.h"

int mod(DataType data,int capacity)
{
  return data%capacity;
}

//初始化
void HashInit(Hashtable *ht,int capacity,Hashfunc hash)
{
  ht->table = (Element *)malloc(sizeof(Element)*capacity);
  assert(ht->table);
  ht->capacity = capacity;
  ht->size = 0;
  ht->hash = hash;

  int i = 0;
  for(i = 0;i<capacity;i++)
  {
    ht->table[i].stata = EMPTY;
  }
}


//查找

int HashFind(Hashtable *ht,DataType data)
{
  //int index = ht->hash(data,ht->capacity);
  int origin_index = ht->hash(data,ht->capacity);
  int index = origin_index;
  int i = 1;
  while(1)
  {
    if(ht->table[index].stata == EMPTY)
      return -1;
    if(ht->table[index].stata == DATA && ht->table[index].data == data)
    return -1;
    
    index = (origin_index + i*i)%ht->capacity;
    i++;
    //index = (index + 1)% ht->capacity;
  }
  return -1;
}

//删除

int HashDelete(Hashtable *ht,DataType data)
{
  int res = HashFind(ht,data);
  if(res == -1)
    return -1;
  //int index = ht->hash(data,ht->capacity);
   
  int origin_index = ht->hash(data,ht->capacity);
  int index = origin_index;
  int i = 1;
  while(1)
  {
    if(ht->table[index].stata == DATA && ht->table[index].data == data)
    {
      ht->table[index].stata = DELETE;
      ht->size--;
      return 1;
    }
    index = (origin_index + i*i)%ht->capacity;
    i++;
    //index = (index + 1)%ht->capacity;
  }
}


//插入

void BuyMemory(Hashtable *ht)
{
  double res = ht->size/(double)ht->capacity;
  if((res-0.7)<EXP && (res-0.7)>-EXP)
  {
    Hashtable Newhash;
    HashInit(&Newhash,ht->capacity*2,ht->hash);

    int i = 0;
    for(i = 0;i<ht->capacity;i++)
    {
      hashInsert(&Newhash,ht->table[i].data);
    }
    free(ht->table);
    ht->table = Newhash.table;
    ht->capacity = ht->capacity *2;
  }
  else 
    return;
}

int hashInsert(Hashtable *ht,DataType data)
{
  int res = HashFind(ht,data);
  if(res == 1)
    return -1;
  BuyMemory(ht);
 // int index = ht->hash(data,ht->capacity);

  int origin_index = ht->hash(data,ht->capacity);
  int index = origin_index;
  int i = 1;
  while(1)
  {
    if(ht->table[index].stata !=DATA)
    {
      ht->table[index].data = data;
      ht->table[index].stata = DATA;
      ht->size++;
      return 1;
    }
    index = (origin_index + i*i)%ht->capacity;
    i++;
    //index = (index +1)%ht->capacity;
  }
  return 1;
}

void Hashdestory(Hashtable *ht)
{
  free(ht->table);
}

void Test()
{
  Hashtable ht;
  HashInit(&ht,11,mod);
  hashInsert(&ht,37);
  hashInsert(&ht,25);
  hashInsert(&ht,14);
  hashInsert(&ht,36);
  hashInsert(&ht,49);
  hashInsert(&ht,68);
  hashInsert(&ht,57);
  hashInsert(&ht,11);

  int i = 0;
  for(i = 0;i<ht.capacity;i++)
  {
    printf("%d ",ht.table[i].data);
  }
  printf("\n");
  Hashdestory(&ht);
}

